package Top_Interview_Questions_Review._007Sliding_Window;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/9 12:01
 * <p>
 * 看官方题解
 */
public class _0003 {

    public static void main(String[] args) {
        _0003 test = new _0003();
        test.lengthOfLongestSubstring1("pwwkew");
    }


    /**
     * 优化的滑动窗口
     * 写的有点巧妙
     */
    public int lengthOfLongestSubstring1(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }



    /**
     * 滑动窗口
     */
    public int lengthOfLongestSubstring(String s) {


        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }

    /**
     * 功能描述: 比较规范的滑动窗口
     */
    public int lengthOfLongestSubstring3(String s) {
        Map<Character, Integer> window = new HashMap<Character, Integer>();

        int left = 0, right = 0;
        int res = 0; // 记录结果
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 进行窗口内数据的一系列更新
            window.put(c, window.getOrDefault(c, 0) + 1);
            // 判断左侧窗口是否要收缩

            while (window.get(c).compareTo(1) > 0) {
                char d = s.charAt(left);
                left++;
                // 进行窗口内数据的一系列更新

                window.put(d, window.get(d) - 1);
            }
            // 在这里更新答案
            res = Math.max(res, right - left);
        }
        return res;
    }

}
